package algorithm.dynamic;

public class Jump {

    public int jump(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 当前的步数
        int jump = 0;
        // 当前到达最远的位置
        int cur = 0;
        // 多跳一步，能到达最远的位置
        int next = 0;
        for (int i = 0; i < arr.length; i++) {
            if (cur < i) {
                // 当前步数+1
                jump++;
                // 更新能到达最远的位置
                cur = next;
            }
            // 每个位置能到达的最远位置
            next = Math.max(next, i + arr[i]);
        }
        return jump;
    }
}
